// Package skipset is a high-performance, scalable and concurrent-safe implementation of skip-list.
package skipset

import "sync/atomic"

const (
	maxHeight           = 16
	defaultHeaderHeight = 3
)

// Set 集合
type Set interface {
	Len() int
	Insert(value int64) bool
	Remove(value int64) bool
	Contains(value int64) bool
	Range(f func(value int64) bool)
}

// 跳表集合
type skipSet struct {
	header       *skipNode // 头结点，高度为最大高度
	length       int64     // 元素个数
	headerHeight int64     // 跳表头结点高度
}

// NewSkipSet 创建有序集合
func NewSkipSet() Set {
	header := newSkipNode(0, maxHeight)
	header.states.Append(fullyLinked)
	return &skipSet{
		header:       header,
		headerHeight: defaultHeaderHeight,
	}
}

// Len 返回有序集合中元素个数
func (s *skipSet) Len() int {
	return int(atomic.LoadInt64(&s.length))
}

// Insert 并发安全地插入元素，成功返回则 true
// 失败原因：另一个线程已经插入了同一元素
// 当该元素已经在跳表中，但尚未完全连接，则等待其完全连接
func (s *skipSet) Insert(value int64) bool {
	nodeLevel := s.randomHeight()         // 随机高度
	var prevs, nexts [maxHeight]*skipNode // 记录新节点各层的前驱和后继
	for {
		heightFound := s.findNode(value, &prevs, &nexts) // 寻找值为 value 的结点
		if heightFound != -1 {                           // 该节点在跳表中已存在
			nodeFound := nexts[heightFound] // 取出该节点
			if nodeFound.states.HasAny(marked) {
				// 如果该节点被标记，说明另一个线程正在删除该节点
				// 那么就下个循环继续尝试
				continue
			}
			for !nodeFound.states.HasAny(fullyLinked) {
				// 如果该节点尚未完全连接，说明该节点正在被其他线程插入到跳表
				// 那么就等待其插入完成，即完全连接后再报告插入失败
			}
			// 然后报告插入失败
			return false
		}
		// 跳表中没有值为 value 的结点，正常插入
		var (
			highestLocked = -1      // 当前线程锁住的最大层数
			collided      = false   // 是否发生了冲突
			prev, next    *skipNode // 前驱后继
			upperPrev     *skipNode // 上一层的前驱，用于实现同一节点只锁一次
		)
		// 从下到上（从近到远）锁住该结点的所有前驱
		for l := 0; !collided && l < nodeLevel; l++ {
			prev, next = prevs[l], nexts[l]
			if prev != upperPrev { // go 锁不可重入，同一节点只锁一次
				prev.mtx.Lock()
				highestLocked = l
				upperPrev = prev
			}
			collided = isInsertionCollided(prev, next, l) // 冲突检测
		}
		// 如果冲突了，解锁重试
		if collided {
			unlockInt64(prevs, highestLocked)
			continue
		}

		// 创建并连接结点
		nn := newSkipNode(value, nodeLevel)
		for layer := 0; layer < nodeLevel; layer++ {
			nn.storeNext(layer, nexts[layer])
			prevs[layer].atomicStoreNext(layer, nn)
		}
		nn.states.Append(fullyLinked)     // 连接完成，更新状态
		unlockInt64(prevs, highestLocked) // 解锁前驱
		atomic.AddInt64(&s.length, 1)     // 更新跳表元素个数
		return true                       // 报告插入成功
	}
}

// Remove 并发安全地删除值为 value 的结点
// 返回节点原本是否存在
func (s *skipSet) Remove(value int64) bool {
	var (
		targetNode   *skipNode            // 记录被删除结点
		isMarked     bool                 // 当前线程是否已标记该结点
		prevs, nexts [maxHeight]*skipNode // 记录被删除结点每一层的前驱和后继们
	)
	for {
		heightFound := s.findNode(value, &prevs, &nexts) // 查找值为 value 的结点
		// 没有被标记 &&  (没找到 || 找到了但没有处于全连接且未标记状态 || 该结点高度-1 不再是查到的结点高度)
		if !isMarked && (heightFound == -1 || !nexts[heightFound].states.HasOnlySpecified(fullyLinked|marked, fullyLinked) || (int(nexts[heightFound].height)-1) != heightFound) {
			return false // 报告删除失败
		}
		// 本线程在上一轮标记了该结点
		// This process has marked the node, or we can find this node in the skip-list
		if !isMarked { // 第一次尝试删除
			targetNode = nexts[heightFound]
			targetNode.mtx.Lock()                 // 锁住被删除结点
			if targetNode.states.HasAny(marked) { // 如果被删除结点已被其他线程标记，解锁，交给改线程进行处理
				targetNode.mtx.Unlock()
				return false
			}
			targetNode.states.Append(marked) // 标记该节点
			isMarked = true
		}
		// 物理删除改结点
		var (
			highestLocked = -1      // 当前线程锁住的最大层数
			collided      = false   // 是否冲突
			prev, next    *skipNode // 前驱后继
			upperPrev     *skipNode // 上一层的前驱，用于实现同一节点只锁一次
		)
		// 从下到上（从近到远）锁住该结点的所有前驱
		for l := 0; !collided && (l <= heightFound); l++ {
			prev, next = prevs[l], nexts[l]
			if prev != upperPrev { // the node in this l could be locked by previous loop
				prev.mtx.Lock()
				highestLocked = l
				upperPrev = prev
			}
			collided = isRemovingCollided(prev, next, l)
		}
		// 如果冲突了，解锁重试
		if collided {
			unlockInt64(prevs, highestLocked)
			continue
		}
		// 更新所有前驱的后继为被 targetNode 的后继
		for l := heightFound; l >= 0; l-- {
			prevs[l].atomicStoreNext(l, targetNode.loadNext(l))
		}
		targetNode.mtx.Unlock()           // 物理删除完成，解锁 targetNode
		unlockInt64(prevs, highestLocked) // 解锁前驱
		atomic.AddInt64(&s.length, -1)    // 更新跳表元素个数
		return true
	}
}

// Contains 判断跳表中是否有值为 value 的结点
func (s *skipSet) Contains(value int64) bool {
	current := s.header                                                // header: 最左结点
	for l := int(atomic.LoadInt64(&s.headerHeight)) - 1; l >= 0; l-- { // 从上到下搜索
		next := current.atomicLoadNext(l)
		for next != nil && next.lessThan(value) { // 同一层从左到右搜索，直到 next.Value >= 给定 value
			current = next
			next = current.atomicLoadNext(l)
		}

		// 检查跳表中是否已经存在值为 value 的结点
		if next != nil && next.equalTo(value) {
			return next.states.HasOnlySpecified(fullyLinked|marked, fullyLinked) // 并且该结点完全连接并且没有被标记
		}
	}
	return false // 没找到
}

// Range 对跳表中每一个正常连接的节点进行访问
// 如果 f 对 value 操作返回 false，中断遍历
func (s *skipSet) Range(f func(value int64) bool) {
	current := s.header.atomicLoadNext(0)
	for current != nil { // 从左到右搜索
		if !current.states.HasOnlySpecified(fullyLinked|marked, fullyLinked) { // 只访问完全连接并且没有被标记的结点
			current = current.atomicLoadNext(0)
			continue
		}
		if !f(current.value) { // 根据 f 返回值确定是否继续访问
			break
		}
		current = current.atomicLoadNext(0)
	}
}

// 从左上到右下搜索值为 value 的结点
// 在每一层 l 设置 prevs 和 nexts 的值，使得 prevs[l] < value <= nexts[l]
// 如果搜到了，则返回从左上到右下搜索过程中第一次发现 value 节点的高度
// 如果没有搜到，则返回 -1
func (s *skipSet) findNode(value int64, prevs *[maxHeight]*skipNode, nexts *[maxHeight]*skipNode) int {
	current := s.header                                                // header: 最左结点
	for l := int(atomic.LoadInt64(&s.headerHeight)) - 1; l >= 0; l-- { // 从上到下搜索
		next := current.atomicLoadNext(l)
		for next != nil && next.lessThan(value) { // 同一层从左到右搜索，直到 next.Value >= 给定 value
			current = next
			next = current.atomicLoadNext(l)
		}
		prevs[l] = current // 最大的 < 给定 value 的结点
		nexts[l] = next    // 最小的 >= 给定 value 的结点

		// 检查跳表中是否已经存在值为 value 的结点
		if next != nil && next.equalTo(value) {
			return l
		}
	}
	return -1 // 没找到
}

// 生成并返回随机高度，如果大于 s 的最大高度，则更新 s 的最大高度
func (s *skipSet) randomHeight() int {
	// 生成 1..=maxHeight 的随机高度
	nodeHeight := randomHeight()
	// 如果生成高度大于 header 高度，则更新 header 高度
	for { // 自旋锁
		headerHeight := atomic.LoadInt64(&s.headerHeight)
		if int64(nodeHeight) <= headerHeight {
			break
		}
		if atomic.CompareAndSwapInt64(&s.headerHeight, headerHeight, int64(nodeHeight)) {
			break
		}
	}
	return nodeHeight
}

// 插入时检查冲突，冲突可能情况
// 1. prev 或者 next 被标记，说明其他线程正在删除
// 2. prev 的后继不再是 next，说明其他线程刚刚将新结点插到 prev 和 next 之间
func isInsertionCollided(prev, next *skipNode, l int) bool {
	return prev.states.HasAny(marked) || (next != nil && next.states.HasAny(marked)) || prev.loadNext(l) != next
}

// 删除时检查冲突，冲突可能情况
// 1. prev 被标记，说明其他线程正在删除
// 2.  prev 的后继不再是 next，说明其他线程刚刚将新结点插到 prev 和 next 之间
func isRemovingCollided(prev, next *skipNode, l int) bool {
	return prev.states.HasAny(marked) || prev.loadNext(l) != next
}
